package main

import (
	"fmt"
	"math/rand"
	"time"
)

// 冒泡排序
func sort1(arr []int) {
	for i := 0; i < len(arr)-1; i++ {
		flag := true
		for j := 0; j < len(arr)-1-i; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
				flag = false
			}
		}
		if flag {
			break
		}
	}
}

// 选择排序
func sort2(arr []int) {
	for i := 0; i < len(arr); i++ {
		minIndex := i
		for j := i + 1; j < len(arr); j++ {
			if arr[j] < arr[minIndex] {
				minIndex = j
			}
		}
		arr[i], arr[minIndex] = arr[minIndex], arr[i]
	}
}

// 插入排序
func sort3(arr []int) {
	if len(arr) <= 1 {
		return
	}
	for i := 1; i < len(arr); i++ {
		value := arr[i] // 临时保存变量，插入后后移动一个元素会把arr[i]覆盖。
		j := i - 1
		for j >= 0 && value < arr[j] { // 插入，并且移动元素
			arr[j+1] = arr[j]
			j--
		}
		arr[j+1] = value
	}
}
func main() {
	rand.Seed(time.Now().Unix())
	//const length = 80000
	const length = 2
	arr := make([]int, 0, length)
	for i := 0; i < length; i++ {
		arr = append(arr, rand.Intn(100))
	}
	fmt.Println("before sort:", arr)
	now := time.Now()
	sort3(arr)
	fmt.Println(time.Now().Sub(now).Seconds())
	fmt.Println("after sort:", arr)

}
